//
// Created by liushuai on 2021/1/27.
//

#include "longestSubstring.h"

int longestSubstring(string x, string y) {
<<<<<<< HEAD:cxx/algorithm/src/longestSubstring.cc
    if(x.empty()||y.empty())
        return 0;
    int x_size = x.size();
    int y_size = y.size();

    vector<int> rows(y_size + 1, 0);
    vector<vector<int>> DP(x_size + 1, rows);

    for (int i = 0; i < x.size(); i++) {
        for (int j = 0; j < y.size(); j++) {
            if(!i||!j)
                DP[i][j] = 0;
            else{
                if(x[i]==y[j])
                    DP[i][j] = DP[i-1][j-1]+1;
                else
                    DP[i][j] = DP[i-1][j]>DP[i][j-1]?DP[i-1][j]:DP[i][j-1];
            }
        }
    }
    return DP[x_size-1][y_size-1];

}
=======
  if (x.empty() || y.empty()) return 0;
  int x_size = x.size();
  int y_size = y.size();

  vector<int> rows(y_size + 1, 0);
  vector<vector<int>> DP(x_size + 1, rows);

  for (int i = 0; i < x.size(); i++) {
    for (int j = 0; j < y.size(); j++) {
      if (!i || !j)
        DP[i][j] = 0;
      else {
        if (x[i] == y[j])
          DP[i][j] = DP[i - 1][j - 1] + 1;
        else
          DP[i][j] = DP[i - 1][j] > DP[i][j - 1] ? DP[i - 1][j] : DP[i][j - 1];
      }
    }
  }
  return DP[x_size - 1][y_size - 1];
}
>>>>>>> dev:cxx/algorithm/common/src/longestSubstring.cc
